import java.util.ArrayList;
import java.util.List;

/**
 * 77. Combinations 组合
 * https://leetcode.com/problems/combinations/
 */
class ComBinations {
    private final List<List<Integer>> ans = new ArrayList<>();
    private final List<Integer> path = new ArrayList<>();
    private int k;

    /**
     * 方法：回溯法
     * Args: 
     *   n - 整数范围的上限
     *   k - 组合的大小
     * Returns: 所有可能的k个数的组合
     * Time: O(C(n,k) * k) - 需要生成C(n,k)个组合，每个组合需要O(k)时间
     * Space: O(k) - 递归栈的深度最多为k
     */
    public List<List<Integer>> combine(int n, int k) {
        this.k = k;
        backtrack(n);
        return ans;
    }

    private void backtrack(int i){
        int d = k - path.size(); // 还要选 d 个数
        if(d == 0){
            ans.add(new ArrayList<>(path));
            return;
        }
        for(int j = i; j>= d; j--){
            path.add(j);
            backtrack(j - 1);
            path.remove(path.size() - 1);
        }
    }
}